package 算法复习课.手动造轮子.list;

import java.util.Iterator;
import java.util.LinkedList;

/**
 * 单向链表
 *
 * @author linhao
 * @date created in 3:20 下午 2020/10/20
 */
public class SingleLinkedList<T> implements List<T> {

    private Node<T> head;
    private int size;
    private int modCount;

    private class Node<T> {
        private T data;
        private Node nextNode;

        public Node(T data, Node nextNode) {
            this.data = data;
            this.nextNode = nextNode;
        }
    }


    private SingleLinkedList() {
        Node node = new Node(null, null);
        head = new Node(node, null);
    }

    @Override
    public Object add(Object o) {
        if (head == null) {
            throw new RuntimeException("head is null");
        }
        Node temp = head;
        while (temp.nextNode != null) {
            temp = temp.nextNode;
        }
        temp.nextNode = new Node(o, null);
        size++;
        return o;
    }

    @Override
    public void set(int index, Object data) {
        if (head == null) {
            throw new RuntimeException("head is null");
        }
        if (index > size) {
            throw new RuntimeException("index is error input");
        }
        Node temp = head;
        int k = 0;
        while (index != k && temp.nextNode != null) {
            k++;
            temp = temp.nextNode;
        }
        Node p = temp.nextNode;
        if (index == k) {
            temp.nextNode = new Node(data, p);
            size++;
            return;
        }
        throw new RuntimeException("index should not bigger than size");
    }

    @Override
    public T remove(int index) {
        if (head == null) {
            throw new RuntimeException("head is null");
        }
        if (index > size) {
            throw new RuntimeException("index is error input");
        }
        Node temp = head;
        Node preTemp = null;
        int k = 0;
        while (index != k && temp.nextNode != null) {
            k++;
            preTemp = temp;
            temp = temp.nextNode;
        }
        if (index == k && temp.nextNode != null) {
            Node p = temp.nextNode;
            preTemp.nextNode = p;
            temp = null;
            size--;
        }
        return null;
    }

    @Override
    public int indexOf(Object data) {
        if (head == null) {
            throw new RuntimeException("head is null");
        }
        Node temp = head;
        int i = 0;
        while (null != temp && temp.data != data) {
            temp = temp.nextNode;
            i++;
        }
        if (null == temp) {
            return -1;
        }
        if (data == temp.data) {
            return i;
        }
        return -1;
    }

    @Override
    public boolean contain(Object data) {
        return indexOf(data) != -1;
    }

    @Override
    public T get(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        int i = 0;
        Node temp = head.nextNode;
        while (temp != null && i != index) {
            temp = temp.nextNode;
            i++;
        }
        return (T) temp.data;
    }

    @Override
    public void grow() {
        return;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void display() {
        Node temp = head.nextNode;
        while (temp != null) {
            System.out.println(temp.data);
            temp = temp.nextNode;
        }
    }

    @Override
    public Iterator iterator() {
        return new Itr();
    }

    @Override
    public boolean ensureListSafe() {
        return true;
    }

    private class Itr implements Iterator {
        int cursor;
        Node lastRet;
        volatile int exceptModCount;

        private Itr(){
            this.cursor=0;
            lastRet=head;
        }

        @Override
        public boolean hasNext() {
            return cursor<size;
        }

        @Override
        public Object next() {
            if (cursor > size) {
                throw new RuntimeException("no next item");
            }
            if (cursor == 0) {
                lastRet = head.nextNode;
            } else {
                lastRet = lastRet.nextNode;
            }
            cursor++;
            return lastRet.data;
        }
    }

    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(1);
        singleLinkedList.add(2);
        singleLinkedList.add(3);
        singleLinkedList.remove(2);
        singleLinkedList.remove(1);
        singleLinkedList.add(4);
        singleLinkedList.add(5);
        singleLinkedList.add(6);
        singleLinkedList.display();

        System.out.println(singleLinkedList.indexOf(2));
        System.out.println(singleLinkedList.get(1));
        Iterator iterator = singleLinkedList.iterator();
        while(iterator.hasNext()){
            Object obj = iterator.next();
            System.out.print(obj+" ");
        }

    }
}
